Introduction to Machine Learning

Chapter 12: Regression Foundations, KNN, and Regression Trees

Introduction

This chapter marks the transition from classification to regression problems.

Classification vs. Regression:

Aspect Classification Regression
Output Type Discrete labels Continuous values
Examples Spam detection, image classification House price prediction, temperature forecasting
Loss Functions Cross-entropy, Gini impurity MSE, MAE, RMSE
Evaluation Metrics Accuracy, Precision, Recall, F1, AUC-ROC RMSE, MAE, R²

The key distinction is therefore the type of target variable being predicted.

This lecture covers:

Real-world Regression Examples:

These examples illustrate that regression is useful whenever the target is a numerical quantity.

2. Theory

2.1 From Classification to Regression

While classification and regression are different types of prediction problems, they follow a similar overall ML pipeline:

  1. Data collection
  2. Data preprocessing
    • Handle missing values, outliers
    • Feature scaling (critical for models using gradient descent)
    • Encoding (relevant for mixed features)
  3. Train-test split (or train-val-test)
  4. Model training
    • Choose algorithm (e.g., linear regression, regression trees, gradient boosting)
    • Optimize using regression-specific loss (e.g., MSE, MAE)
  5. Evaluation
    • Use regression metrics: RMSE, MAE, R²
    • Not classification metrics: accuracy, F1-score, AUC-ROC

2.2 Evaluation: How Do We Measure Regression Performance?

A regression model is rarely exactly right. Instead of counting correct predictions, we measure how far the predictions are from the true values. The three standard metrics differ in how they treat large errors.

Unlike classification, which commonly uses metrics such as accuracy and F1-score, regression requires different evaluation metrics:

Common Regression Metrics:

2.3 Mean Squared Error (MSE)

\[ \text{MSE} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2 \]

2.4 Root Mean Squared Error (RMSE)

\[ \text{RMSE} = \sqrt{\text{MSE}} = \sqrt{\frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2} \]

2.5 Mean Absolute Error (MAE)

\[ \text{MAE} = \frac{1}{n} \sum_{i=1}^n |y_i - \hat{y}_i| \]

Choosing Between MSE, RMSE, and MAE:

Metric Sensitive to Outliers Interpretable Units Differentiable
MSE ✅ Yes (heavily) ❌ No (squared units) ✅ Yes
RMSE ✅ Yes (heavily) ✅ Yes (original units) ❌ No (due to square root)
MAE ❌ No (robust) ✅ Yes (original units) ❌ No (due to absolute value)

The choice of metric depends on whether large errors should be penalized strongly or treated more evenly.

2.6 Regression Algorithms – Course Roadmap

This course will cover several regression algorithms, including:

  1. K-Nearest Neighbors (KNN) Regressor
    • Non-parametric, instance-based
    • Simple extension from KNN classification
  2. Regression Trees (Decision Trees)
    • Non-parametric, rule-based
    • Splits to minimize MSE
  3. Ordinary Least Squares (OLS) Regression
    • Parametric, linear model
    • Closed-form solution or gradient descent
  4. Polynomial Regression
    • Extending OLS for non-linear relationships
    • Feature engineering approach
  5. Regularized Regression (Ridge & Lasso)
    • OLS with shrinkage/penalty
    • Prevents overfitting, automatic feature selection
  6. Gradient Boosting for Regression
    • Ensemble method (combines multiple trees)
    • State-of-the-art performance

2.7 K-Nearest Neighbors (KNN) Regressor

Like KNN classification, KNN regression identifies the nearest neighbors of a query point. Instead of assigning a class label, however, it predicts a continuous value by averaging the target values of those neighbors.

How KNN Regression Works:

Thus, KNN regression bases each prediction on the local neighborhood around the query point.

Characteristics:

2.8 KNN Regression Example

Consider a small dataset with TV, Radio, and Newspaper advertising budgets, where Sales is the target variable:

# TV Radio Newspaper Sales
R1230.137.869.2?
R244.539.345.110.4
R317.245.969.39.3
R4151.541.358.518.5
R5180.810.858.412.9
R68.748.9757.2

Example predictions: Using the nearest neighbors identified for each value of K, we obtain the following predictions:

KNN Regression Visualization A one-dimensional K-nearest neighbors regression example showing sales values, a query point at position 16, and predictions for K equal to 1, 3, and 5. KNN Regression Visualization Estimating sales for an unknown query position using nearby observations Sales values at different positions Observed points along a one-dimensional feature line 0 5 10 15 20 25 30 Query: 16 7 9 12 18 25 30 Position Sales Predict from nearby points Predictions by neighborhood size 1 K = 1 Nearest neighbor Position 15 · Sales 18 Prediction 18 direct estimate 3 K = 3 Nearest neighbors 10 (12) · 15 (18) · 20 (25) Average prediction 18.33 (12 + 18 + 25) / 3 5 K = 5 Nearest neighbors 5 (9) · 10 (12) · 15 (18) 20 (25) · 25 (30) Average prediction 18.8 (9 + 12 + 18 + 25 + 30) / 5 i Smoothing insight As K increases, more observations influence the estimate and the prediction becomes smoother. s*

2.9 Regression Tree

Decision trees can also be used when the response variable is numerical. Regression trees operate much like classification trees, but the target, leaf prediction, and splitting criterion are different:

Regression Trees vs Classification Trees:

Aspect Classification Trees Regression Trees
Target Variable Categorical Continuous
Leaf Node Value Majority class (voting) Average of training data in that leaf
Impurity Measure Gini impurity, Entropy Sum of squared deviations from the mean
Splitting Criterion Maximize information gain Minimize MSE (or variance)

The main change from classification to regression is how leaf predictions and split quality are defined.

Key Insight: In a regression tree, the value of a leaf node is the average of the training targets that fall into that leaf. A typical impurity measure is the sum of the squared deviations from the leaf mean.

Important Notes:

2.10 Regression Tree Example

Consider a dataset for predicting the number of golf players from weather conditions:

Day Outlook Temp. Humidity Wind Golf Players
1SunnyHotHighWeak25
2SunnyHotHighStrong30
3OvercastHotHighWeak46
4RainMildHighWeak45
5RainCoolNormalWeak52
6RainCoolNormalStrong23
7OvercastCoolNormalStrong43
8SunnyMildHighWeak35
9SunnyCoolNormalWeak38
10RainMildNormalWeak46
11SunnyMildNormalStrong48
12OvercastMildHighStrong52
13OvercastHotNormalWeak44
14RainMildHighStrong30

Now consider the same dataset again, but with Temperature represented as a numeric predictor:

Day Outlook Temp. Humidity Wind Golf Players
1Sunny42HighWeak25
2Sunny38HighStrong30
3Overcast40HighWeak46
4Rain32HighWeak45
5Rain12NormalWeak52
6Rain14NormalStrong23
7Overcast15NormalStrong43
8Sunny28HighWeak35
9Sunny10NormalWeak38
10Rain24NormalWeak46
11Sunny22NormalStrong48
12Overcast26HighStrong52
13Overcast36NormalWeak44
14Rain30HighStrong30

Effect of Tree Depth:

Thus, tree depth controls a bias–variance trade-off: deeper trees fit the training data more closely but can also overfit.

2.11 Overfitting in Regression Trees

Overfitting is an important issue with regression trees:

Overfitting in Regression Trees Comparison of an overfit regression tree without regularization and a smoother regression tree with a minimum samples per leaf of ten. Overfitting in Regression Trees Regularization controls model complexity so predictions generalize beyond the training set Without Regularization Overfit model Prediction Training points Complex prediction path Observed data Result Complex, jagged predictions follow nearly every point—including noise. With Regularization min_samples_leaf = 10 Prediction Training points Regularized prediction Observed data Result Simpler, more reasonable model ignores noise and generalizes better. Key insight Without regularization, regression trees can create predictions that obviously overfit the training set. s*

3. Interactive Examples

MSE Calculation Example

Consider a house-price prediction model with the following data:

House Price ($1000s) y Square Feet x
2451400
3121600
2791700
3081875
1991100
2191550
4052350
3242450
3191425
2551700

Suppose the model makes the following predictions:

Actual (y) Square Feet (x) Predicted (ŷ) Error Error²
2451400252-749
3121600273.938.11451.61
2791700284.9-5.934.81
3081875304.13.915.21
1991100219-20400
2191550268.4-49.42440.36
4052350356.348.72371.69
3242450367.3-43.31874.89
3191425254.764.34134.49
2551700284.9-29.9894.01

Calculate MSE:

\[ \text{MSE} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2 = \frac{49 + 1451.61 + 34.81 + 15.21 + 400 + 2440.36 + 2371.69 + 1874.89 + 4134.49 + 894.01}{10} \] \[ = \frac{13176.07}{10} = 1317.607 \]

KNN Regression Visualization

Consider a simple one-dimensional regression problem:

KNN Regression in One Dimension A visual explanation of K nearest neighbors regression for a query point at x equals 4.5, showing predictions for K values 1 through 4. KNN Regression in 1D Predicting a value by averaging the nearest observations QUERY POINT x = 4.5 Observed data and query location The nearest points are selected by horizontal distance from x = 4.5. 0 2 4 6 8 1 2 3 4 5 6 7 8 feature x target y x = 4.5 query How prediction works 1. Measure distance from the query to every observed point. 2. Select the K closest neighbors. 3. Average their target values: ŷ = average of neighbor y values DATASET x: 1, 2, 3, 4, 5, 6, 7, 8 y: 2, 4, 5, 4, 6, 8, 7, 9 Predictions for different values of K Increasing K smooths the estimate by including more nearby observations. K = 1 Nearest neighbor x=4, y=4 Prediction 4 K = 2 Nearest neighbors x=4, y=4 x=5, y=6 Prediction 5 (4 + 6) / 2 K = 3 Nearest neighbors x=3, y=5 x=4, y=4 x=5, y=6 Prediction ≈ 5 (5 + 4 + 6) / 3 K = 4 Nearest neighbors x=2,4 x=3,5 x=4,4 x=5,6 Prediction 4.75 (4 + 5 + 4 + 6) / 4 s*

4. Numerical Solutions

MSE, RMSE, and MAE Calculation

Given the following actual and predicted values:

Actual (y) Predicted (ŷ) Error (y - ŷ) Error² |Error|
1012-242
1514111
2018242
2527-242
3028242

Calculate:

MSE: \[ \text{MSE} = \frac{4 + 1 + 4 + 4 + 4}{5} = \frac{17}{5} = 3.4 \]
RMSE: \[ \text{RMSE} = \sqrt{3.4} \approx 1.84 \]
MAE: \[ \text{MAE} = \frac{2 + 1 + 2 + 2 + 2}{5} = \frac{9}{5} = 1.8 \]

KNN Regression Calculation

Given the following data points (x, y):

(1, 2), (2, 4), (3, 5), (4, 4), (5, 6), (6, 8), (7, 7), (8, 9)

Query point: x = 4.5

Calculate predictions for different K values:

K = 1: \[ \text{One nearest neighbor is } (4, 4) \implies \text{Prediction} = 4 \]
K = 2: \[ \text{Nearest neighbors: } (4, 4), (5, 6) \implies \text{Prediction} = \frac{4 + 6}{2} = 5 \]
K = 3: \[ \text{Nearest neighbors: } (3, 5), (4, 4), (5, 6) \implies \text{Prediction} = \frac{5 + 4 + 6}{3} \approx 5 \]
K = 4: \[ \text{Nearest neighbors: } (2, 4), (3, 5), (4, 4), (5, 6) \implies \text{Prediction} = \frac{4 + 5 + 4 + 6}{4} = 4.75 \]

5. Try It Yourself

Problem 1: MSE and RMSE Calculation

Given the following actual and predicted values:

ActualPredicted
57
108
1516
2019

Tasks:

  1. Calculate MSE
  2. Calculate RMSE
  3. Which metric is easier to interpret and why?

Solution:

  1. Errors: (5-7)=-2, (10-8)=2, (15-16)=-1, (20-19)=1
  2. Squared errors: 4, 4, 1, 1
  3. MSE: (4 + 4 + 1 + 1)/4 = 10/4 = 2.5
  4. RMSE: √2.5 ≈ 1.58
  5. Interpretability: RMSE is easier to interpret because it's in the same units as the target variable (2.5 vs 1.58, where 1.58 is more meaningful)
Problem 2: MAE vs MSE

Given two models with the following errors on a test set:

Model A: Errors = [-3, -2, -1, 0, 1, 2, 3]

Model B: Errors = [-5, -1, -1, 0, 1, 1, 5]

Tasks:

  1. Calculate MAE for both models
  2. Calculate MSE for both models
  3. Which model performs better according to MAE?
  4. Which model performs better according to MSE?
  5. Which metric do you think is more appropriate here and why?

Solution:

  1. MAE:
    • Model A: (3+2+1+0+1+2+3)/7 = 12/7 ≈ 1.71
    • Model B: (5+1+1+0+1+1+5)/7 = 14/7 = 2.0
  2. MSE:
    • Model A: (9+4+1+0+1+4+9)/7 = 28/7 = 4.0
    • Model B: (25+1+1+0+1+1+25)/7 = 54/7 ≈ 7.71
  3. MAE winner: Model A (1.71 < 2.0)
  4. MSE winner: Model A (4.0 < 7.71)
  5. Appropriate metric: Both metrics agree that Model A is better. However, MSE penalizes Model B more heavily for its large errors (-5 and 5), which might be desirable if large errors are particularly bad. MAE is more robust to outliers.
Problem 3: KNN Regression Prediction

Given the following training data (x, y):

(1, 3), (2, 5), (3, 7), (4, 9), (5, 11)

Query point: x = 3.5

Tasks:

  1. What is the prediction when K=1?
  2. What is the prediction when K=2?
  3. What is the prediction when K=3?
  4. As K increases, what happens to the prediction?

Solution:

  1. K=1: Nearest neighbor is (3, 7) or (4, 9). Assuming Euclidean distance, both are equally close (distance=0.5). Typically, we'd pick the first one: Prediction = 7
  2. K=2: Nearest neighbors: (3, 7) and (4, 9). Prediction = (7 + 9)/2 = 8
  3. K=3: Nearest neighbors: (2, 5), (3, 7), (4, 9). Prediction = (5 + 7 + 9)/3 ≈ 7
  4. As K increases: The prediction becomes more smoothed and approaches the average of all y values (7). With K=5, prediction = (3+5+7+9+11)/5 = 7.
Problem 4: Regression Tree Splitting

Consider a simple dataset for predicting house prices based on square footage:

Square FeetPrice ($1000s)
1000200
1200220
1500250
1800300
2000320

Task: If we're building a regression tree with max_depth=1 (one split), where would be the optimal split point to minimize MSE? Calculate the MSE for splits at 1300, 1400, 1600, and 1700 square feet.

Solution:

For each potential split, we calculate the MSE of the predictions:

Split at 1300:

  • Left (≤1300): 1000(200), 1200(220) → mean = 210
  • Right (>1300): 1500(250), 1800(300), 2000(320) → mean = 290
  • MSE = [(200-210)² + (220-210)² + (250-290)² + (300-290)² + (320-290)²]/5
  • = [100 + 100 + 1600 + 100 + 900]/5 = 2800/5 = 560

Split at 1400:

  • Left (≤1400): 1000(200), 1200(220) → mean = 210
  • Right (>1400): 1500(250), 1800(300), 2000(320) → mean = 290
  • MSE = 560 (same as 1300)

Split at 1600:

  • Left (≤1600): 1000(200), 1200(220), 1500(250) → mean = 223.33
  • Right (>1600): 1800(300), 2000(320) → mean = 310
  • MSE = [(200-223.33)² + (220-223.33)² + (250-223.33)² + (300-310)² + (320-310)²]/5
  • = [537.78 + 11.11 + 711.11 + 100 + 100]/5 ≈ 1460/5 = 292

Split at 1700:

  • Left (≤1700): 1000(200), 1200(220), 1500(250), 1800(300) → mean = 242.5
  • Right (>1700): 2000(320) → mean = 320
  • MSE = [(200-242.5)² + (220-242.5)² + (250-242.5)² + (300-242.5)² + (320-320)²]/5
  • = [1806.25 + 506.25 + 56.25 + 3306.25 + 0]/5 = 5775/5 = 1155

Optimal split: At 1600 square feet with MSE = 292 (lowest MSE)

Problem 5: Choosing Evaluation Metric

You are building a model to predict house prices, and your dataset contains some outliers (very expensive houses that are unusual for their size).

Tasks:

  1. Which evaluation metric would you choose: MSE, RMSE, or MAE?
  2. Why is this metric more appropriate?
  3. If you want to heavily penalize large errors (e.g., underestimating the price of an expensive house by a lot), which metric would you choose?

Solution:

  1. Recommended metric: MAE (Mean Absolute Error)
  2. Reason: MAE is more robust to outliers. Since the dataset contains outliers (very expensive houses), MSE and RMSE would be heavily influenced by these extreme values, giving a distorted view of typical model performance. MAE treats all errors equally, regardless of their magnitude.
  3. For penalizing large errors: MSE or RMSE. Both heavily penalize large errors due to the squaring operation. RMSE is often preferred because it's in the same units as the target variable, making it more interpretable.

6. Interactive Quiz

Answer all 5 questions. Click an option for instant feedback.

Your score: 0 / 5

7. Key Takeaways

Classification vs Regression:

Evaluation Metrics:

KNN Regressor:

Regression Trees:

General Insights:

8. Common Pitfalls

️ Evaluation Metrics:

️ KNN Regressor:

️ Regression Trees:

️ General: